package com.lzq.leetcode.s164;

public class 最大间距 {

    public static void main(String[] args) {
        int[] nums = new int[]{1,1,1,1,1,5,5,5,5,5};
        System.out.println(maximumGap(nums));
    }

    public static int maximumGap(int[] nums) {

        // 找到最大值和最小值
        int m = Integer.MAX_VALUE;
        int M = Integer.MIN_VALUE;
        for (int num : nums) {
            m = Math.min(m, num);
            M = Math.max(M, num);
        }
        if (M - m <= 1) return M - m;
        // 计算平均差值
        int len = nums.length;
        int avg = (M - m) / len + 1;
        // 计算桶的个数
        int n = (M - m + avg) / avg;
        // 创建桶
        int[][] buttons = new int[n][2];
        // 遍历初始化桶
        for (int[] button : buttons) {
            button[0] = Integer.MAX_VALUE;
            button[1] = Integer.MIN_VALUE;
        }
        // 遍历所有元素, 将元素放入桶中
        for (int num : nums) {
            // 计算其对应的桶编号
            int bId = (num - m) / avg;
            // 修改桶的值
            buttons[bId][0] = Math.min(num, buttons[bId][0]);
            buttons[bId][1] = Math.max(num, buttons[bId][1]);
        }
        // 遍历桶, 找到最大差值
        int ans = Integer.MIN_VALUE;
        int preMax = buttons[0][1];
        for (int i = 1; i < buttons.length; i++) {
            if (buttons[i][0] != Integer.MAX_VALUE) {
                ans = Math.max(buttons[i][0] - preMax, ans);
                preMax = buttons[i][1];
            }
        }

        return ans;
    }
}
